#ifndef cathlibcpp_list_H
#define cathlibcpp_list_H

// File:       list.h
// Author:     (c) Miles Sabin, 1996
// Purpose:    approximation to ANSI C++ list template


#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_config_H
#include "config.h"
#endif

#ifndef cathlibcpp_iterator_H
#include "iterator.h"
#endif

#ifndef cathlibcpp_listbase_H
#include "listbase.h"
#endif

#ifndef cathlibcpp_newcasts_H
#include "newcasts.h"
#endif

#ifndef cathlibcpp_utility_H
#include "utility.h"
#endif


template<class T>
struct list_node;

template<class T>
class list_iterator;

template<class T>
class list_const_iterator;


template<class T>
class list : private list_base
{
  public:

#   define reference              T&
#   define const_reference        T const&
#   define iterator               list_iterator<T>
#   define const_iterator         list_const_iterator<T>
#   define rev_iterator           reverse_bidirectional_iterator<list_iterator<T>, T, reference>
#   define const_rev_iterator     reverse_bidirectional_iterator<list_const_iterator<T>, T, const_reference>
#   define size_type              size_t
#   define difference_type        ptrdiff_t
#   define value_type             T

    // constructors
    list();
    list(size_type n);
    list(size_type n, T const& value);
    list(iterator const& first, iterator const& last);
    list(T const* first, T const* last);
    list(list<T> const& rhs);
    ~list();

    // accessors
    const_iterator begin() const;
    const_iterator end() const;

    const_rev_iterator rbegin() const;
    const_rev_iterator rend() const;

    const_reference front() const;
    const_reference back() const;

    bool empty() const;
    size_type size() const;
    size_type max_size() const;

    // mutators
    list<T>& operator=(list<T> const& rhs);

    void assign(iterator const& first, iterator const& last);
    void assign(T const* first, T const* last);
    void assign(size_type n, T const& t);

    iterator begin();
    iterator end();

    rev_iterator rbegin();
    rev_iterator rend();

    reference front();
    reference back();

    void push_front(T const& x);
    void push_back(T const& x);

    void pop_front();
    void pop_back();

    iterator insert(iterator const& position, T const& x);
    void insert(iterator const& position, size_type n, T const& x);
    void insert(iterator const& position, iterator const& first, iterator const& last);
    void insert(iterator const& position, T const* first, T const* last);

    void erase(iterator const& position);
    void erase(iterator const& first, iterator const& last);

    void swap(list<T>& x);

    void clear();

    void splice(iterator const& position, list<T>& x);
    void splice(iterator const& position, list<T>& x, iterator const& i);
    void splice(iterator const& position, list<T>& x, iterator const& first, iterator const& last);

    void remove(T const& value);
    void remove_if(bool (*pred)(T const&));

    void unique();
    void unique(bool (*pred)(T const&, T const&));

    void merge(list<T>& x);
    void merge(list<T>& x, bool (*comp)(T const&, T const&));

    void sort();
    void sort(bool (*comp)(T const&, T const&));

    void reverse();

    void resize(size_type sz, T const& c);

#   undef reference
#   undef const_reference
#   undef iterator
#   undef const_iterator
#   undef rev_iterator
#   undef const_rev_iterator
#   undef size_type
#   undef difference_type
#   undef value_type
};


template<class T>
bool operator==(list<T> const& lhs, list<T> const& rhs);

template<class T>
bool operator<(list<T> const& lhs, list<T> const& rhs);


// list iterator

template<class T>
class list_iterator : public bidirectional_iterator<T>
{
  friend class list<T>;
  friend bool operator==(list_iterator<T> const& lhs, list_iterator<T> const& rhs);

  public:

    // constructors
    list_iterator()
      {}
    list_iterator(list_iterator<T> const& rhs)
      : node_(rhs.node_)
      {}

    // accessors
    bool operator==(list_iterator<T> const& rhs) const
      { return node_ == rhs.node_; }

    T& operator*() const
      { return *reinterpret_cast(T*, node_+1); }

#ifndef PROBLEM_MEMBER_ACCESS
    T* operator->() const
      { return reinterpret_cast(T*, node_+1); }
#endif

    // mutators
    list_iterator<T>& operator=(list_iterator<T> const& rhs)
      { node_ = rhs.node_; return *this; }

    list_iterator<T>& operator++()
      { node_ = node_->next_; return *this; }
    list_iterator<T> operator++(int)
      { node_ = node_->next_; return node_->prev_; }

    list_iterator<T>& operator--()
      { node_ = node_->prev_; return *this; }
    list_iterator<T> operator--(int)
      { node_ = node_->prev_; return node_->next_; }

  private:

    list_iterator(list_base_node* node)
      : node_(node)
      {}

    list_base_node* node_;
};


// list const iterator

template<class T>
class list_const_iterator : public bidirectional_iterator<T const>
{
  friend class list<T>;
  friend bool operator==(list_const_iterator<T> const& lhs, list_const_iterator<T> const& rhs);

  public:

    // constructors
    list_const_iterator()
      {}
    list_const_iterator(list_const_iterator<T> const& rhs)
      : node_(rhs.node_)
      {}

    // accessors
    bool operator==(list_const_iterator<T> const& rhs) const
      { return node_ == rhs.node_; }

    T const& operator*() const
      { return *reinterpret_cast(T const*, node_+1); }

#ifndef PROBLEM_MEMBER_ACCESS
    T const* operator->() const
      { return reinterpret_cast(T*, node_+1); }
#endif

    // mutators
    list_const_iterator<T>& operator=(list_const_iterator<T> const& rhs)
      { node_ = rhs.node_; return *this; }

    list_const_iterator<T>& operator++()
      { node_ = node_->next_; return *this; }
    list_const_iterator<T> operator++(int)
      { node_ = node_->next_; return node_->prev_; }

    list_const_iterator<T>& operator--()
      { node_ = node_->prev_; return *this; }
    list_const_iterator<T> operator--(int)
      { node_ = node_->prev_; return node_->next_; }

  private:

    list_const_iterator(list_base_node const* node)
      : node_(node)
      {}

    list_base_node const* node_;
};

#endif
